#coding=utf-8
from math import ceil
#大数乘法
def recursive_multiply(x:int, y:int, n:int)->int:
    if n==1:
        return x*y
    else:
        a = x//pow(10, n//2)
        b = x-a*pow(10, n//2)
        c = y//pow(10, n//2)
        d = y-c*pow(10, n//2)
        ac = recursive_multiply(a, c, ceil(n/2))
        bd = recursive_multiply(b, d, ceil(n/2))
        p = recursive_multiply(a+b, c+d, ceil(n/2)) - ac -bd
    return ac*pow(10, 2*(n//2)) + p*pow(10, n//2) + bd

print(recursive_multiply(13579, 24680, 5))



#求众数
def split(list, dic):
    n = len(list)
    mid = n // 2
    flag = 0
    dic["mid"] = mid
    for i in range(mid + 1):  #处理左边的情况
        if list[i] == list[mid]:
            dic["l"] = i
            break
    if (mid + 1 == n):  #中位数右边只有一个数的情况
        dic["r"] = mid + 1
    for j in range(mid + 1, n):  #处理右边的情况
        if list[j] != list[mid]:
            dic["r"] = j
            flag = 1
            break
        if flag == 0: #即右边都是中位数
            dic["r"] = j + 1


def Mode(list, dic):  #递归处理
    '''
    原理是每一次都比较mid是不是众数
    :param list:
    :param dic:
    :return:
    '''
    split(list, dic)
    s = dic["r"] - dic["l"]
    if s > dic["num"]:
        dic["maxnum"] = list[dic["mid"]]
        dic["num"] = s
    if (dic["l"]) > s:   #如果左边仍有比s长的序列，就可能存在比mid更大的众数
        Mode(list[:dic["l"]], dic)
    if (len(list) - dic["r"]) > s:  #右边同理
        Mode(list[dic["r"]:], dic)

list = [3,2,3,7,7,8,7,7,7]
list.sort()  #列表一定要是有序的
print(f'列表为：{list}')
dic = {"r": 0, "l": 0, "maxnum": 0, "num": -1, "mid": 0}
Mode(list, dic)
if dic["num"] > len(list) /  2:
    print("出现了 %d 次" % dic["num"])
    print("众数是 %d " % dic["maxnum"])
else:
    print("没有众数")